package examination;

import org.junit.Test;

import java.util.ArrayList;

/**
 * Created by zxc on 2018/9/16.
 * 计算字符串中连续出现数字的最大和，字符串以空格“ ”分割，字符串中非数字部分不做统计，
 * 如果字符串中没有数字返回0
 * 示例：1 2 3 为6  2 ks 1 -1 最大和为3
 */
public class ContinuousSum {
     public int getContinuousNumber(String numberStr) {
         //分割字符串
        String[] strs = numberStr.split(" ");
        ArrayList<Integer> numbers = new ArrayList<>();
        for(int i=0; i < strs.length; i++ ){
            // 判断字符串是否是数字？
            if((strs[i].charAt(0) >= 48) && (strs[i].charAt(0) <= 57)){
                numbers.add(Integer.valueOf(strs[i]));
            }
        }
        // ArrayList 转为数组
        Integer[] arrs = numbers.toArray(new Integer[numbers.size()]);
         // 一个数组任意的连续子数组的最大和  https://blog.csdn.net/u014259820/article/details/79628758
         int sum = calMaxSumOfArrayWay1(arrs);
        return  sum;
    }

    /*暴力遍历。从i=0开始到i=a.length-1，开始往后加，遍历所有的子数组，然后比较每一个子数组的和。
    时间复杂度O(n^2)，空间复杂度O(1)。*/
    public int calMaxSumOfArrayWay1(Integer[] a) {
        if (null == a) {
            return 0;
        }
        if (a.length == 1) {
            return a[0];
        }
        Integer sum = a[0];
        Integer temp;
        for (int i = 0; i < a.length - 1; i++) {
            temp = a[i];
            //开始从a[i]往它之后遍历，相加，再跟sum对比
            for (int j = i + 1; j < a.length; j++) {
                temp = temp + a[j];
                if(sum < temp) {
                    sum = temp;
                }
            }
        }
        return sum.intValue();
    }

    /*动态规划。状态方程：max(dp[i]) = getMax(max(dp[i-1]) + a[i], a[i])。我们从头开始遍历数组，遍历到a[i]时，
    最大和可能是max(dp[i-1])+a[i]，也可能是a[i]。时间复杂度O(n)，空间复杂度O(n)。*/

    @Test
    public void getContinuousNumberTest(){
        getContinuousNumber("12 -23 jkds d -32 -56 jk 43 k 34");
    }

}
